← All Articles

[SW Expert Academy] 3135. 홍준이의 사전놀이

Posted on

문제 :

홍준이에게는 소중한 보물이 있다.

바로 ‘영어사전’ 이다.

영어사전을 자주 펼쳐보던 홍준이는 이런 궁금증이 생겼다.

“특정 문자열로 시작하는 단어의 총 갯수는 몇 개일까?”

예를 들어, abcabd는 abc로 시작하는 단어이고, asdfs는 as로 시작하는 단어이지만, asdfs가 abc로 시작하는 단어는 아니다.

홍준이가 가지고 있던 영어 사전에는 단어가 너무 많아서 그 갯수를 세아리는 것은 사실상 불가능하였다.

그래서 홍준이는 새로 사전을 만들어보고자 한다.

홍준이는 빈 공책을 하나 사서, 단어를 추가하면서 위의 질문을 스스로 던지며 놀기로 하였다.

홍준이가 추가하는 단어가 insert 함수의 인자로 주어질 때에, query 함수를 통해 스스로 던진 질문에 답을 하는 프로그램을 작성하자.

작성해야 하는 함수 3가지는 다음과 같다.

C/C++의 경우 void init(void) : 각 테스트케이스 시작마다 호출되는 함수이다.

void insert(int buffer_size, char *buf) : 홍준이가 공책에 추가하는 새로운 단어의 길이(= buffer_size)와 문자열 정보(= buf)가 인자로 주어지는 함수이다.

int query(int buffer_size, char *buf) : buffer_size 길이의 buf 문자열이 주어졌을 때에, 현재 공책에 적힌 단어들 중 buf로 시작하는 단어의 갯수를 반환하는 함수이다.

Java의 경우 void init() : 각 테스트케이스 시작마다 호출되는 함수이다.

void insert(int buffer_size, String buf) : 홍준이가 공책에 추가하는 새로운 단어의 길이(= buffer_size)와 문자열 정보(= buf)가 인자로 주어지는 함수이다.

int query(int buffer_size, String buf) : buffer_size 길이의 buf 문자열이 주어졌을 때에, 현재 공책에 적힌 단어들 중 buf로 시작하는 단어의 갯수를 반환하는 함수이다.


[ 코드 작성시 주의점 ]

  1. Main 부분과 User Code 부분으로 구성되어 있다. - Main 부분 : 수정할 수 없는 코드이며, 채점 시 주어지는 코드 그대로 사용된다.

    - User Code 부분 : 실제 응시자가 작성해야 하는 코드이며, 제출 시에는 코드 내에 라이브러리 함수 뿐 아니라 표준 입출력 함수도 포함되어서는 안된다.

  2. Local PC에서 프로그래밍시 유의사항 - Main 부분의 코드를 복사해서 사용해야 한다.

    - input.txt를 사용하시기 위해서는 Main 부분의 코드 내에 표준 입력을 파일로 전환하는 코드(주석처리 되어 있음)의 주석을 풀어서 사용해야 한다.

    - User Code 부분의 코드를 작성하신 후 서버에 제출하실 때는 디버깅을 위한 라이브러리 함수뿐 아니라 표준 입출력 함수를 모두 삭제해야 한다.

  3. 문제 내에 제약조건을 모두 명시하지 않으므로 주어지는 코드를 분석해야 한다.
  4. 코드는 개발 언어에 따라 상이할 수 있으므로, 작성할 언어를 기준으로 분석해야 한다.

입력 :

첫째 줄에 테스트케이스의 개수를 나타내는 정수 T가 주어진다. (1≤T≤50)

각 테스트케이스마다 첫째 줄에 홍준이가 수행할 연산의 횟수를 나타내는 정수 N이 주어진다. ( 1 ≤ N ≤ 105 )

이후 N개의 줄에 걸쳐서 홍준이가 수행할 연산의 정보가 순서대로 주어진다.

각 연산 정보는 자연수 P와 문자열 S가 공백을 사이에 두고 주어진다.

P가 1이면, 홍준이가 공책에 문자열 S를 적는 것이다.

P가 2이면, 현재까지 공책의 단어들 중 S로 시작하는 단어의 갯수를 묻는 것이다.

S의 길이는 1 이상 10 이하임이 보장된다.


출력 :

각 테스트케이스마다 ‘#T’(T는 테스트케이스의 번호)를 출력하고, P가 2인 연산들에 대해 답을 공백 하나를 사이에 두고 순서대로 출력한다.



풀이 :

=> 삼성 SW 역량테스트 “B”형 테스트 문제

문제 난이도는 어렵지 않은 문제였다. 문자열을 사전 형태로 만들어 해당 접두어를 가진 단어의 개수를 알 수 잇도록 트라이(Trie) 자료구조 형태를 사용하면 문제에 쉽게 접근할 수 있었다.

문제에서 주어진 3가지의 함수를 구현하여 단어 추가, 접두어 포함 단어 개수를 파악할 수 있도록 해야한다,

  • init() : 테스트 케이스 실행 전 초기화 함수이다. 내 코드에서는 트라이 최상단 루트 노드를 초기화해주는 과정을 본 함수에서 실행한다.
  • insert() : 매개변수로 들어온 문자열을 트라이 구조에 삽입하는 함수이다.
  • query() : 매개벼수로 들어온 문자열의 접두어를 가진 단어의 개수를 반환하는 함수이다.

트라이 노드 구조에는 두가지 속성이 있다 childcnt의 경우 본 노드 자식 노드 개수를 나타내는 변수로써 해당 접두어를 가진 단어의 개수를 의미하기도 한다. 그리고 포인터 배열 childs[26]의 경우는 각 알파벳별 자식 노드 포인터를 저장하는 배열이다.



코드 :

코드 보기/접기 
#define NULL 0

typedef struct Node {
    int childcnt = 0;
    Node *childs[26]{NULL};
};
Node *root;

void init(void) {
    root = new Node;
}

void insert(int buffer_size, char *buf) {
    Node *curptr = root;
    for (int k = 0; k < buffer_size; k++) {
        if (!curptr->childs[buf[k] - 'a']) curptr->childs[buf[k] - 'a'] = new Node;
        curptr = curptr->childs[buf[k] - 'a'];

        curptr->childcnt++;
    }
}

int query(int buffer_size, char *buf) {
    Node *curptr = root;
    for (int k = 0; k < buffer_size; k++) {
        curptr = curptr->childs[buf[k] - 'a'];
        if (!curptr) return 0;
    }
    return curptr->childcnt;
}


AlgorithmalgorithmSW ExpertC++